class Solution {
public:
    string find(string& s,int len){
        int base = 31;
        unsigned long long hash = 0;
        unsigned long long prime = 1;

        unordered_set<long> st;
        for(int i = 0;i < len;i++){
            hash = hash * base + s[i];
            prime *= base;
        }
        st.insert(hash);
        for(int i = len;i < s.size();i++){
            hash = hash * base + s[i] - prime * s[i-len];
            if(st.find(hash) != st.end()){
        
                return s.substr(i-len+1,len);
            }
            st.insert(hash);
        }
        return "";
    }
    string longestDupSubstring(string s) {
        int left = 0;
        int right = s.size() - 1;
        string ret;
        while(left <= right){
            int mid = (left + right + 1) / 2;
            string ans = find(s,mid);
            
            if(ans != ""){
                left = mid + 1;
                ret = ans;
            }else{
                right = mid - 1;
            }
        }
        return ret;
    }
};
